from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    ## 双指针
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        a = head
        b = head
        
        ## 先走n步
        for _ in range(n):
            if a.next:
                a = a.next
            else:
                return head.next
        
        while a.next:
            a =a.next
            b = b.next
        b.next  = b.next.next

        return head
    
    def removeNthFromEnd1(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(-1)
        dummy.next = head

        fast = dummy
        for _ in range(n):
            fast = fast.next
        
        slow = dummy
        while fast.next:
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next





        